1608B - Build the Permutation - CodeForces Solution


constructive algorithms greedy *1200

Please click on ads to support us..

Python Code:

t = int(input())

for i in range(t):

    n, a, b = map(int, input().split())

    c = [j + 1 for j in range(n)]

    ans = []

    if a + b > n - 2 or abs(a-b) > 1:
        print(-1)
    else:
        if b > a:
            for j in range(min(a,b) + 1):
                ans.append(c[-1])
                ans.append(c[0])
                c.pop()
                c.pop(0)
            ans += c

        elif a > b:
            for j in range(min(a, b) + 1):
                ans.append(c[0])
                ans.append(c[-1])
                c.pop(0)
                c.pop()
            c.reverse()
            ans += c

        else:
            for j in range(a):
                ans.append(c[0])
                ans.append(c[-1])
                c.pop(0)
                c.pop()
            ans.append(c[0])
            c.pop(0)
            ans += c

        for j in range(len(ans)):
            print(ans[j], end = ' ')
        print()






C++ Code:

#define ll long long
#define MAXN 200010
#define INF 0x3f3f3f3f
#include <bits/stdc++.h>
using namespace std;

int main(){
#ifdef _DEBUG
    freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
#endif
#define int ll
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;
    while (t--) {
        int n, a, b;
        cin >> n >> a >> b;
        vector<int> v;
        int i = 1, j = n;
        while (i < j) {
            v.push_back(i);
            v.push_back(j);
            ++i, --j;
        }
        if (i == j) {
            v.push_back(i);
        }
        int up = 0, down = 0;
        if (up == a && down == b) {
            sort(v.begin(), v.end());
            for (int i = 0; i < n; ++i) {
                cout << v[i] << " \n"[i == n - 1];
            }
            goto next;
        }
        for (int i = 1; i < (int) v.size() - 1; ++i) {
            if (v[i] > v[i-1] && v[i] > v[i+1]) {
                ++up;
                if (up == a && down == b) {
                    sort(v.begin() + i + 1, v.end());
                    reverse(v.begin() + i + 1, v.end());
                    for (int i = 0; i < n; ++i) {
                        cout << v[i] << " \n"[i == n - 1];
                    }
                    goto next;
                }
            }
            else if (v[i] < v[i-1] && v[i] < v[i+1]) {
                ++down;
                if (up == a && down == b) {
                    sort(v.begin() + i + 1, v.end());
                    for (int i = 0; i < n; ++i) {
                        cout << v[i] << " \n"[i == n - 1];
                    }
                    goto next;
                }
            }
        }
        v.clear();
        i = 1, j = n;
        while (i < j) {
            v.push_back(j);
            v.push_back(i);
            ++i, --j;
        }
        if (i == j) {
            v.push_back(i);
        }
        up = 0, down = 0;
        for (int i = 1; i < (int) v.size() - 1; ++i) {
            if (v[i] > v[i-1] && v[i] > v[i+1]) {
                ++up;
                if (up == a && down == b) {
                    sort(v.begin() + i + 1, v.end());
                    reverse(v.begin() + i + 1, v.end());
                    for (int i = 0; i < n; ++i) {
                        cout << v[i] << " \n"[i == n - 1];
                    }
                    goto next;
                }
            }
            else if (v[i] < v[i-1] && v[i] < v[i+1]) {
                ++down;
                if (up == a && down == b) {
                    sort(v.begin() + i + 1, v.end());
                    for (int i = 0; i < n; ++i) {
                        cout << v[i] << " \n"[i == n - 1];
                    }
                    goto next;
                }
            }
        }
        cout << "-1\n";
    next:;
    }

    return 0;
}


Comments

Submit
0 Comments
More Questions

1178D - Prime Graph
1711D - Rain
534A - Exam
1472A - Cards for Friends
315A - Sereja and Bottles
1697C - awoo's Favorite Problem
165A - Supercentral Point
1493A - Anti-knapsack
1493B - Planet Lapituletti
747B - Mammoth's Genome Decoding
1591C - Minimize Distance
1182B - Plus from Picture
1674B - Dictionary
1426C - Increase and Copy
520C - DNA Alignment
767A - Snacktower
1365A - Matrix Game
714B - Filya and Homework
31A - Worms Evolution
1691A - Beat The Odds
433B - Kuriyama Mirai's Stones
892A - Greed
32A - Reconnaissance
1236D - Alice and the Doll
1207B - Square Filling
1676D - X-Sum
1679A - AvtoBus
1549A - Gregor and Cryptography
918C - The Monster
4B - Before an Exam